因为题面不一样,作者也懒得改,所以以下兽人指侏儒,骑士指精灵
1.40分思路
兽王给每个勇士选择的对手都是 1 号兽人,那么,GM所指定骑士的顺序就一定是兽人的编号,即第i个骑士对第i个兽人。现在我们只需找一种骑士的排法,使得胜场数最大。
贪心的想,最强的骑士对比他弱的兽人中最强的,第二强的骑士对比他弱的兽人中最强的······直到某一位骑士无法打败任何一人。可以排序后用单调性优化。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 500000;
int n,a[ MAXN + 5 ],p[ MAXN + 5 ],v[ MAXN + 5 ];
bool cmp( const int &x , const int &y ) {
return x > y;
}
int main( ) {
//freopen("Kralj.in","r",stdin);
//freopen("Kralj.out","w",stdout);
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&a[ i ]);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&p[ i ]);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&v[ i ]);
sort( p + 1 , p + n + 1 , cmp );
sort( v + 1 , v + n + 1 , cmp );
int Ans = 0 , last = 1;
for( int i = 1 ; i <= n ; i ++ ) {
for( int j = last ; j <= n ; j ++ ) {
if( v[ i ] > p[ j ] ) {
Ans ++;
last = j + 1;
break;
}
if( j == n && v[ i ] < p[ j ] ) last = n + 1;
}
if( last == n + 1 ) break;
}
printf("%d",Ans);
return 0;
}
2.100分思路
假设骑士走到后就停下,不继续向前找兽人,我们用表示与之前的节点骑士的个数。
当一个区间内的骑士多于该区间的兽人时,可表示为:
移项得:
令,则。由定义可得,的意思是这个点之前的骑士与兽人的数量之差,我们设。则一定没有骑士从 走到 。证明如下:
因为最小,所以对于任意,,即m之前的骑士都能找到对应的兽人。所以我们可以在 处剖开链,贪心模拟。
我们从 开始,用 表示没有坐好的骑士的集合。每次到达新的点,先加入停留在这个点上的所有骑士。现在可能有多个骑士对一个兽人,显然我们应该用实力高于这个兽人中实力最小的骑士来面对它,可以用二分求出,答案加 。剩下的骑士向前移。如果没有骑士大于兽人的实力,就将骑士实力最弱的留下当炮灰。
注意跑环时,就是,特判一下。
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
const int MAXN = 500000;
int n,a[ MAXN + 5 ],p[ MAXN + 5 ],v[ MAXN + 5 ];
int pre[ MAXN + 5 ],s[ MAXN + 5 ];
int Min = 0x3f3f3f3f , Min_dex;
vector< int > vec[ MAXN + 5 ];
set< int > Set;
int solve( int x ) {
int Ans = 0 , tot = 1;
while( tot <= n ) {
for( int i = 0 ; i < vec[ x ].size( ) ; i ++ )
Set.insert( vec[ x ][ i ] );
auto it = Set.lower_bound( p[ x ] );
if( it == Set.end() )
Set.erase( Set.begin() );
else {
Set.erase( it );
Ans ++;
}
tot ++;
x = ( x + 1 ) > n ? 1 : x + 1;
}
return Ans;
}
int main( ) {
//freopen("Kralj.in","r",stdin);
//freopen("Kralj.out","w",stdout);
scanf("%d",&n);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&a[ i ]);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&p[ i ]);
for( int i = 1 ; i <= n ; i ++ )
scanf("%d",&v[ i ]);
for( int i = 1 ; i <= n ; i ++ ) {
pre[ a[ i ] ] ++;
vec[ a[ i ] ].push_back( v[ i ] );
}
for( int i = 1 ; i <= n ; i ++ ) {
pre[ i ] += pre[ i - 1 ];
s[ i ] = pre[ i ] - i;
if( s[ i ] < Min ) {
Min = s[ i ];
Min_dex = i;
}
}
int cut = ( Min_dex + 1 ) > n ? 1 : ( Min_dex + 1 );
printf("%d",solve( cut ));
return 0;
}